{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #All Elements in Two Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getAllElements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两棵二叉搜索树中的所有元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你&nbsp;<code>root1</code> 和 <code>root2</code>&nbsp;这两棵二叉搜索树。请你返回一个列表，其中包含&nbsp;<strong>两棵树&nbsp;</strong>中的所有整数并按 <strong>升序</strong> 排序。.</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/12/29/q2-e1.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [2,1,4], root2 = [1,0,3]\n",
    "<strong>输出：</strong>[0,1,1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/12/29/q2-e5-.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root1 = [1,null,8], root2 = [8,1]\n",
    "<strong>输出：</strong>[1,1,8,8]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每棵树的节点数在&nbsp;<code>[0, 5000]</code> 范围内</li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [all-elements-in-two-binary-search-trees](https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [all-elements-in-two-binary-search-trees](https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4]\\n[1,0,3]', '[1,null,8]\\n[8,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def replenish(self, stack: List[TreeNode]) -> None:\n",
    "        node: TreeNode = stack.pop().right\n",
    "        while node is not None:\n",
    "            stack.append(node)\n",
    "            node = node.left\n",
    "            \n",
    "            \n",
    "    def clearRest(self, stack: List[TreeNode], A: List[int]) -> None:\n",
    "        while len(stack) > 0:\n",
    "            A.append(stack[-1].val)\n",
    "            self.replenish(stack)\n",
    "            \n",
    "        \n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        stack1: List[TreeNode] = [TreeNode(0, None, root1)]\n",
    "        stack2: List[TreeNode] = [TreeNode(0, None, root2)]\n",
    "        self.replenish(stack1)\n",
    "        self.replenish(stack2)\n",
    "            \n",
    "        ans: List[int] = []\n",
    "        while len(stack1) > 0 and len(stack2) > 0:\n",
    "            if stack1[-1].val <= stack2[-1].val:\n",
    "                ans.append(stack1[-1].val)\n",
    "                self.replenish(stack1)\n",
    "            else:\n",
    "                ans.append(stack2[-1].val)\n",
    "                self.replenish(stack2)\n",
    "                \n",
    "        self.clearRest(stack1, ans)\n",
    "        self.clearRest(stack2, ans)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        f = [root1,root2]\n",
    "        res = []\n",
    "        while f:\n",
    "            v = f.pop(0)\n",
    "            if not v:\n",
    "                continue\n",
    "            res.append(v.val)\n",
    "            if v.left:\n",
    "                f.append(v.left)\n",
    "            if v.right:\n",
    "                f.append(v.right)\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def ite(node):\n",
    "            if not node:\n",
    "                yield None\n",
    "            stack = [node]\n",
    "            while stack:\n",
    "                cur = stack[-1]\n",
    "                while cur.left:\n",
    "                    stack.append(cur.left)                   \n",
    "                    cur = cur.left\n",
    "                    stack[-2].left = None\n",
    "                head = stack.pop()\n",
    "                if head.right:\n",
    "                    stack.append(head.right)\n",
    "                yield head.val\n",
    "            yield None\n",
    "        res = []\n",
    "        ite1,ite2 = ite(root1), ite(root2)\n",
    "        left, right = next(ite1), next(ite2)\n",
    "        while left!=None and right!=None:\n",
    "            if left < right:\n",
    "                res.append(left)\n",
    "                left = next(ite1)\n",
    "            else:\n",
    "                res.append(right)\n",
    "                right = next(ite2)\n",
    "        if left!=None:\n",
    "            res.append(left)\n",
    "            res.extend([e for e in ite1])\n",
    "        if right!=None:\n",
    "            res.append(right)\n",
    "            res.extend([e for e in ite2])\n",
    "        if res[-1] == None:\n",
    "            res.pop()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        from collections import deque\n",
    "        def all_nums(root):\n",
    "            if root==None:\n",
    "                return []\n",
    "            ans=[]\n",
    "            stack=[root]\n",
    "            p=stack[-1]\n",
    "            while len(stack)>0:\n",
    "                p=stack[-1]\n",
    "                if p.left:\n",
    "                    stack.append(p.left)\n",
    "                    p.left=None\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    ans.append(p.val)\n",
    "                    if p.right:\n",
    "                        stack.append(p.right)\n",
    "                        p.right=None\n",
    "\n",
    "            return ans\n",
    "        ans=all_nums(root1)+all_nums(root2)\n",
    "        return sorted(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getNext(self, s):\n",
    "        while s:\n",
    "            top = s.pop()\n",
    "            if top.left:\n",
    "                left = top.left\n",
    "                top.left = None\n",
    "                s.append(top)\n",
    "                s.append(left)\n",
    "                continue\n",
    "            if top.right:\n",
    "                s.append(top.right)\n",
    "            return top.val\n",
    "        return None\n",
    "\n",
    "\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        s1 = [root1] if root1 is not None else []\n",
    "        s2 = [root2] if root2 is not None else []\n",
    "        a, b, result = None, None, []\n",
    "        while s1 or s2:\n",
    "            if a is None:\n",
    "                a = self.getNext(s1)\n",
    "            if b is None:\n",
    "                b = self.getNext(s2)\n",
    "            print(a, b)\n",
    "            if a is not None and b is not None:\n",
    "                if a < b:\n",
    "                    result.append(a)\n",
    "                    a = None\n",
    "                else:\n",
    "                    result.append(b)\n",
    "                    b = None\n",
    "                continue\n",
    "            if a is not None:\n",
    "                result.append(a)\n",
    "                a = None\n",
    "            if b is not None:\n",
    "                result.append(b)\n",
    "                b = None\n",
    "        if a is not None:\n",
    "            result.append(a)\n",
    "        if b is not None:\n",
    "            result.append(b)\n",
    "        return result                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def inorderTravel(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            \n",
    "            stack = []\n",
    "            res = []\n",
    "            node = root\n",
    "            while stack or node:\n",
    "                while node:\n",
    "                    stack.append(node)\n",
    "                    node = node.left\n",
    "                node = stack.pop()\n",
    "                res.append(node.val)\n",
    "                node = node.right\n",
    "            return res\n",
    "        \n",
    "        res = []\n",
    "        list1, list2 = inorderTravel(root1), inorderTravel(root2)\n",
    "        m, n = len(list1), len(list2)\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n:\n",
    "\n",
    "            tmp1 = list1[i]\n",
    "            tmp2 = list2[j]\n",
    "            if tmp1 < tmp2:\n",
    "                res.append(tmp1)\n",
    "                i += 1\n",
    "            else:\n",
    "                res.append(tmp2)\n",
    "                j += 1\n",
    "        \n",
    "        if i != m:\n",
    "            res += list1[i:]\n",
    "        elif j != n:\n",
    "            res += list2[j:]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode):\n",
    "        def inorder(root):\n",
    "            p, stack = root, []\n",
    "            while p or stack:\n",
    "                if p:\n",
    "                    stack.append(p)\n",
    "                    p = p.left\n",
    "                else:\n",
    "                    p = stack.pop()\n",
    "                    yield p.val\n",
    "                    p = p.right\n",
    "        \n",
    "        tree1, tree2, res = inorder(root1), inorder(root2), []\n",
    "        val1, val2 = next(tree1, None), next(tree2, None)\n",
    "        while not(val1 is None and val2 is None):\n",
    "            if val1 is not None and (val2 is None or val1 <= val2):\n",
    "                res.append(val1)\n",
    "                val1 = next(tree1, None)\n",
    "            elif val2 is not None and (val1 is None or val2 < val1):\n",
    "                res.append(val2)\n",
    "                val2 = next(tree2, None)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "\n",
    "        # 中序遍历然后小的丢进结果里\n",
    "        stack_1 = []\n",
    "        stack_2 = []\n",
    "        self.push_node_to_stack(stack_1, root1)\n",
    "        self.push_node_to_stack(stack_2, root2)\n",
    "\n",
    "        res = []\n",
    "        while len(stack_1) != 0 and len(stack_2) != 0:\n",
    "            node_1 = stack_1.pop()\n",
    "            node_2 = stack_2.pop()\n",
    "            if node_1.val > node_2.val:\n",
    "                node = node_2\n",
    "                stack_1.append(node_1)\n",
    "                if node.right:\n",
    "                    self.push_node_to_stack(stack_2, node.right)\n",
    "            else:\n",
    "                node = node_1\n",
    "                stack_2.append(node_2)\n",
    "                if node.right:\n",
    "                    self.push_node_to_stack(stack_1, node.right)\n",
    "            res.append(node.val)\n",
    "        self.push_left_node(res, stack_1)\n",
    "        self.push_left_node(res, stack_2)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def push_node_to_stack(self, stack: [], node: TreeNode):\n",
    "        while node:\n",
    "            stack.append(node)\n",
    "            node = node.left\n",
    "\n",
    "    def push_left_node(self, res, stack):\n",
    "        while len(stack) != 0:\n",
    "            node = stack.pop()\n",
    "            if node.right:\n",
    "                self.push_node_to_stack(stack, node.right)\n",
    "            res.append(node.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        if root1:\n",
    "            stack = [root1]\n",
    "            while stack:\n",
    "                node = stack.pop()\n",
    "                if node.val is not None:\n",
    "                    result.append(node.val)\n",
    "                if node.left is not None:\n",
    "                    stack.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    stack.append(node.right)\n",
    "\n",
    "        if root2:\n",
    "            stack = [root2]\n",
    "            while stack:\n",
    "                node = stack.pop()\n",
    "                if node.val is not None:\n",
    "                    result.append(node.val)\n",
    "                if node.left is not None:\n",
    "                    stack.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    stack.append(node.right)\n",
    "\n",
    "        return sorted(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        result = []\n",
    "\n",
    "        def dfs(root):\n",
    "            stack = [root]\n",
    "            while stack:\n",
    "                node = stack.pop()\n",
    "                if node.val is not None:\n",
    "                    result.append(node.val)\n",
    "                if node.left is not None:\n",
    "                    stack.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    stack.append(node.right)\n",
    "\n",
    "        if root1:\n",
    "            dfs(root1)\n",
    "        if root2:\n",
    "            dfs(root2)\n",
    "        return sorted(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        s1 = [root1] if root1 != None else []\n",
    "        s2 = [root2] if root2 != None else []\n",
    "        \n",
    "        def toList(s1):\n",
    "            res = []\n",
    "            while s1:\n",
    "                tmp = s1[-1]\n",
    "                if tmp.left != None :\n",
    "                    s1.append(tmp.left)\n",
    "                    tmp.left = None \n",
    "                elif tmp.right != None :\n",
    "                    s1.append(tmp.right)\n",
    "                    tmp.right = None\n",
    "                else:\n",
    "                    s1.pop()\n",
    "                    res.append(tmp.val)\n",
    "            return res\n",
    "        ans = toList(s1)+toList(s2)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        if root1:\n",
    "            stack1.append(root1)\n",
    "        if root2:\n",
    "            stack2.append(root2)\n",
    "\n",
    "        results = []\n",
    "        v1 = self.forward(stack1)\n",
    "        v2 = self.forward(stack2)\n",
    "        while v1 is not None and v2 is not None:\n",
    "            if v1 <= v2:\n",
    "                results.append(v1)\n",
    "                v1 = self.forward(stack1)\n",
    "            else:\n",
    "                results.append(v2)\n",
    "                v2 = self.forward(stack2)\n",
    "        while v1 is not None:\n",
    "            results.append(v1)\n",
    "            v1 = self.forward(stack1)\n",
    "        while v2 is not None:\n",
    "            results.append(v2)\n",
    "            v2 = self.forward(stack2)\n",
    "        return results\n",
    "\n",
    "    def forward(self, stack) -> int:\n",
    "        res = None\n",
    "        while stack:\n",
    "            top = stack[-1]\n",
    "            if top.left:\n",
    "                stack.append(top.left)\n",
    "                top.left = None\n",
    "                continue\n",
    "            res = top.val\n",
    "            stack.pop()\n",
    "            if top.right:\n",
    "                stack.append(top.right)\n",
    "            break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        t1 = BSTIterator(root1)\n",
    "        t2 = BSTIterator(root2)\n",
    "        res = []\n",
    "        while t1.hasNext() and t2.hasNext():\n",
    "            if t1.stk[-1].val < t2.stk[-1].val:\n",
    "                res.append(t1.next())\n",
    "            else:\n",
    "                res.append(t2.next())\n",
    "        \n",
    "        while t1.hasNext():\n",
    "            res.append(t1.next())\n",
    "        while t2.hasNext():\n",
    "            res.append(t2.next())\n",
    "        return res\n",
    "\n",
    "class BSTIterator:\n",
    "\n",
    "    def __init__(self, root: Optional[TreeNode]):\n",
    "        self.stk = []\n",
    "        self.pushLeftBranch(root)\n",
    "\n",
    "    def pushLeftBranch(self, p):\n",
    "        while p:\n",
    "            self.stk.append(p)\n",
    "            p = p.left\n",
    "\n",
    "    def next(self) -> int:\n",
    "        p = self.stk.pop()\n",
    "        self.pushLeftBranch(p.right)\n",
    "        return p.val\n",
    "\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        return self.stk != []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "\n",
    "        def tree_node(root):\n",
    "            stack = []\n",
    "            res = []\n",
    "            while root or stack:\n",
    "                while root:\n",
    "                    stack.append(root)\n",
    "                    root = root.left\n",
    "                root = stack.pop()\n",
    "                res.append(root.val)\n",
    "                root = root.right\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        result = sorted(tree_node(root1) + tree_node(root2))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def dd(q):\n",
    "            node = q.pop()\n",
    "            ans.append(node.val)\n",
    "            node = node.right\n",
    "            while node:\n",
    "                q.append(node)\n",
    "                node = node.left\n",
    "        q1 = []\n",
    "        q2 = []\n",
    "        ans = []\n",
    "        while root1:\n",
    "            q1.append(root1)\n",
    "            root1 = root1.left\n",
    "        while root2:\n",
    "            q2.append(root2)\n",
    "            root2 = root2.left\n",
    "        while q1 and q2:\n",
    "            if q1[-1].val > q2[-1].val:\n",
    "                dd(q2)\n",
    "            else:\n",
    "                dd(q1)\n",
    "        while q1:\n",
    "            dd(q1)\n",
    "        while q2:\n",
    "            dd(q2)           \n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        stack1, stack2 = [], []\n",
    "        p1, p2 = root1, root2\n",
    "\n",
    "        # 中序遍历的迭代实现\n",
    "        while p1 or p2 or stack1 or stack2:\n",
    "            # 先遍历 p1和p2左节点\n",
    "            while p1:\n",
    "                stack1.append(p1)\n",
    "                p1 = p1.left\n",
    "            while p2:\n",
    "                stack2.append(p2)\n",
    "                p2 = p2.left\n",
    "\n",
    "            # 此时 p1, p2都为 None, 需要判断 stack1 和 stack2\n",
    "            # 注意：这时候 stack1和 stack2 至少有 1 个不为None\n",
    "            if not stack2 or (stack1 and stack1[-1].val <= stack2[-1].val):\n",
    "                p1 = stack1.pop()\n",
    "                res.append(p1.val)\n",
    "                p1 = p1.right\n",
    "            else:\n",
    "                p2 = stack2.pop()\n",
    "                res.append(p2.val)\n",
    "                p2 = p2.right        \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def inorder_traversal_to_iter(node):\n",
    "    stack = []\n",
    "    while stack or node:\n",
    "        if node:\n",
    "            stack.append(node)\n",
    "            node = node.left\n",
    "        else:\n",
    "            node = stack.pop()\n",
    "            yield node.val\n",
    "            node = node.right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        # 生成两棵二叉搜索树的中序遍历迭代器\n",
    "        lst1 = inorder_traversal_to_iter(root1)\n",
    "        lst2 = inorder_traversal_to_iter(root2)\n",
    "\n",
    "        ans = []\n",
    "        val1 = next(lst1) if root1 else None\n",
    "        val2 = next(lst2) if root2 else None\n",
    "\n",
    "        if val1 is not None and val2 is not None:\n",
    "            while True:\n",
    "                if val1 <= val2:\n",
    "                    ans.append(val1)\n",
    "                    try:\n",
    "                        val1 = next(lst1)\n",
    "                    except StopIteration:\n",
    "                        try:\n",
    "                            while True:\n",
    "                                ans.append(val2)\n",
    "                                val2 = next(lst2)\n",
    "                        except StopIteration:\n",
    "                            break\n",
    "                else:\n",
    "                    ans.append(val2)\n",
    "                    try:\n",
    "                        val2 = next(lst2)\n",
    "                    except StopIteration:\n",
    "                        try:\n",
    "                            while True:\n",
    "                                ans.append(val1)\n",
    "                                val1 = next(lst1)\n",
    "                        except StopIteration:\n",
    "                            break\n",
    "        elif val1 is None:\n",
    "            try:\n",
    "                while True:\n",
    "                    ans.append(val2)\n",
    "                    val2 = next(lst2)\n",
    "            except StopIteration:\n",
    "                pass\n",
    "        elif val2 is None:\n",
    "            try:\n",
    "                while True:\n",
    "                    ans.append(val1)\n",
    "                    val1 = next(lst1)\n",
    "            except StopIteration:\n",
    "                pass\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "        dfs(root1, l1)\n",
    "        dfs(root2, l2)\n",
    "        return sorted(l1 + l2)\n",
    "\n",
    "def dfs(root: TreeNode, nodes:list):\n",
    "    if not root:\n",
    "        return\n",
    "    nodes.append(root.val)\n",
    "    dfs(root.left, nodes)\n",
    "    dfs(root.right, nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def traverse(node: Optional[TreeNode]) -> Iterator[int]:\n",
    "            if node:\n",
    "                if node.left:\n",
    "                    yield from traverse(node.left)\n",
    "                yield node.val\n",
    "                if node.right:\n",
    "                    yield from traverse(node.right)\n",
    "\n",
    "        result = []\n",
    "        list1, list2 = list(traverse(root1)), list(traverse(root2))\n",
    "        i1 = i2 = 0\n",
    "        while i1 < len(list1) and i2 < len(list2):\n",
    "            if list1[i1] < list2[i2]:\n",
    "                result.append(list1[i1])\n",
    "                i1 += 1\n",
    "            else:\n",
    "                result.append(list2[i2])\n",
    "                i2 += 1\n",
    "        while i1 < len(list1):\n",
    "            result.append(list1[i1])\n",
    "            i1 += 1\n",
    "        while i2 < len(list2):\n",
    "            result.append(list2[i2])\n",
    "            i2 += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def traverse(node: Optional[TreeNode]) -> Iterator[int]:\n",
    "            if node:\n",
    "                yield from traverse(node.left)\n",
    "                yield node.val\n",
    "                yield from traverse(node.right)\n",
    "\n",
    "        result = []\n",
    "        list1, list2 = list(traverse(root1)), list(traverse(root2))\n",
    "        i1 = i2 = 0\n",
    "        while i1 < len(list1) and i2 < len(list2):\n",
    "            if list1[i1] < list2[i2]:\n",
    "                result.append(list1[i1])\n",
    "                i1 += 1\n",
    "            else:\n",
    "                result.append(list2[i2])\n",
    "                i2 += 1\n",
    "        while i1 < len(list1):\n",
    "            result.append(list1[i1])\n",
    "            i1 += 1\n",
    "        while i2 < len(list2):\n",
    "            result.append(list2[i2])\n",
    "            i2 += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return helper(root.left) + [root.val] + helper(root.right)\n",
    "        res = helper(root1) + helper(root2)\n",
    "        res.sort()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    #中序遍历\n",
    "    def inorder(self, root, nums):\n",
    "        if not root : return \n",
    "\n",
    "        self.inorder(root.left, nums)\n",
    "        nums.append(root.val)\n",
    "        self.inorder(root.right, nums)\n",
    "        return\n",
    "\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        v1 = []\n",
    "        v2 = []\n",
    "        #遍历列表\n",
    "        self.inorder(root1, v1)\n",
    "        self.inorder(root2, v2)\n",
    "\n",
    "        #排序组装\n",
    "        i ,j = 0, 0\n",
    "        result = []\n",
    "        n, m = len(v1)-1, len(v2)-1\n",
    "        while i <= n or j <= m:\n",
    "            if j > m or (i <= n and (v1[i] <= v2[j])):\n",
    "                result.append(v1[i])     \n",
    "                i+=1\n",
    "            else:\n",
    "                result.append(v2[j])\n",
    "                j += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        self.traverse(root1,ans1)\n",
    "        self.traverse(root2,ans2)\n",
    "\n",
    "        ans = ans1 + ans2\n",
    "        ans.sort()\n",
    "        return ans\n",
    "    \n",
    "    def traverse(self,root,ans):\n",
    "        if not root:\n",
    "            return \n",
    "            \n",
    "        \n",
    "        self.traverse(root.left,ans)\n",
    "        ans.append(root.val)\n",
    "        self.traverse(root.right,ans)\n",
    "\n",
    "        \n",
    "        # return \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def traverse(self, node: TreeNode, in_order: List[int]):\n",
    "        if node:\n",
    "            self.traverse(node.left, in_order)\n",
    "            in_order.append(node.val)\n",
    "            self.traverse(node.right, in_order)\n",
    "\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        in_order1 = [] \n",
    "        self.traverse(root1, in_order1)\n",
    "        in_order2 = []\n",
    "        self.traverse(root2, in_order2)\n",
    "        return sorted(in_order1 + in_order2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        # O(m + n)\n",
    "        # O(m + n)\n",
    "        l1 = self.inorderTraversal(root1)\n",
    "        l2 = self.inorderTraversal(root2)\n",
    "        n1 = len(l1)\n",
    "        n2 = len(l2)\n",
    "        res = []\n",
    "        idx1 = 0\n",
    "        idx2 = 0\n",
    "        while idx1 < n1 and idx2 < n2:\n",
    "            if l1[idx1] < l2[idx2]:\n",
    "                res += [l1[idx1]]\n",
    "                idx1 += 1\n",
    "            else:\n",
    "                res += [l2[idx2]]\n",
    "                idx2 += 1\n",
    "        if idx1 == n1:\n",
    "            res += l2[idx2:]\n",
    "        else:\n",
    "            res += l1[idx1:]\n",
    "        return res\n",
    "\n",
    "    def inorderTraversal(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        else:\n",
    "            return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        return heapq.merge((f := lambda r: r and [*f(r.left), r.val, *f(r.right)] or [])(root1), f(root2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        \n",
    "\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        self.traverse(root1)\n",
    "        self.traverse(root2)\n",
    "        return sorted(self.res)\n",
    "        \n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traverse(root.left)\n",
    "        self.res.append(root.val)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "\n",
    "        self.vals_1 = []\n",
    "        self.vals_2 = []\n",
    "        self.vals = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        if root1 != None:\n",
    "            self.dp_1(root1)\n",
    "            # return self.vals_1\n",
    "        if root2 != None:\n",
    "\n",
    "            self.dp_2(root2)\n",
    "        if root1 == None:\n",
    "            return self.vals_2\n",
    "        \n",
    "        if root2 == None:\n",
    "            return self.vals_1\n",
    "        # print(self.vals_1)\n",
    "        # print()\n",
    "        while True: \n",
    "            # print(i,j)\n",
    "            if self.vals_1[i] < self.vals_2[j]:\n",
    "                \n",
    "                self.vals.append(self.vals_1[i])\n",
    "                \n",
    "                i += 1\n",
    "                if i == len(self.vals_1):\n",
    "                    self.vals.extend(self.vals_2[j:])\n",
    "                    break\n",
    "                # i += 1\n",
    "            else:\n",
    "                \n",
    "                self.vals.append(self.vals_2[j])\n",
    "                \n",
    "                j += 1\n",
    "                if j == len(self.vals_2):\n",
    "                    self.vals.extend(self.vals_1[i:])\n",
    "                    break\n",
    "        \n",
    "        return self.vals\n",
    "\n",
    "    def dp_1(self,node):\n",
    "\n",
    "        if node.left != None:\n",
    "\n",
    "            self.dp_1(node.left)\n",
    "\n",
    "        self.vals_1.append(node.val)\n",
    "\n",
    "        if node.right != None:\n",
    "\n",
    "            self.dp_1(node.right)\n",
    "    \n",
    "    def dp_2(self,node):\n",
    "\n",
    "        if node.left != None:\n",
    "\n",
    "            self.dp_2(node.left)\n",
    "\n",
    "        self.vals_2.append(node.val)\n",
    "\n",
    "        if node.right != None:\n",
    "\n",
    "            self.dp_2(node.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        q = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            q.append(root.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root1)\n",
    "        dfs(root2)\n",
    "        res = sorted(q)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def f(root: TreeNode) -> List[int]:\n",
    "            ans = []\n",
    "            def g(curr: TreeNode):\n",
    "                if not curr: return\n",
    "                g(curr.left)\n",
    "                ans.append(curr.val)\n",
    "                g(curr.right)\n",
    "            g(root)\n",
    "            return ans\n",
    "        xs1, xs2 = f(root1), f(root2)\n",
    "        n1, n2 = len(xs1), len(xs2)\n",
    "        ans = []\n",
    "        i1, i2 = 0, 0\n",
    "        while i1 < n1 and i2 < n2:\n",
    "            if xs1[i1] < xs2[i2]:\n",
    "                ans.append(xs1[i1])\n",
    "                i1 += 1\n",
    "            else:\n",
    "                ans.append(xs2[i2])\n",
    "                i2 += 1\n",
    "        while i1 < n1:\n",
    "            ans.append(xs1[i1])\n",
    "            i1 += 1\n",
    "        while i2 < n2:\n",
    "            ans.append(xs2[i2])\n",
    "            i2 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def inorder(node: TreeNode, res: List[int]):\n",
    "            if node:\n",
    "                inorder(node.left, res)\n",
    "                res.append(node.val)\n",
    "                inorder(node.right, res)\n",
    "\n",
    "        nums1, nums2 = [], []\n",
    "        inorder(root1, nums1)\n",
    "        inorder(root2, nums2)\n",
    "\n",
    "        merged = []\n",
    "        p1, n1 = 0, len(nums1)\n",
    "        p2, n2 = 0, len(nums2)\n",
    "        while True:\n",
    "            if p1 == n1:\n",
    "                merged.extend(nums2[p2:])\n",
    "                break\n",
    "            if p2 == n2:\n",
    "                merged.extend(nums1[p1:])\n",
    "                break\n",
    "            if nums1[p1] < nums2[p2]:\n",
    "                merged.append(nums1[p1])\n",
    "                p1 += 1\n",
    "            else:\n",
    "                merged.append(nums2[p2])\n",
    "                p2 += 1\n",
    "        return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        def get(p):\n",
    "            if p is None:\n",
    "                return []\n",
    "            return get(p.left)+[p.val]+get(p.right)\n",
    "        q1=get(root1)\n",
    "        q2=get(root2)\n",
    "        print(q1)\n",
    "        print(q2)\n",
    "        if len(q1)==0:\n",
    "            return q2\n",
    "        if len(q2)==0:\n",
    "            return q1\n",
    "        i,j=0,0\n",
    "        res=[]\n",
    "        while(i<len(q1) and j<len(q2)):\n",
    "            if q1[i]<q2[j]:\n",
    "                res.append(q1[i])\n",
    "                \n",
    "                i+=1\n",
    "            elif q1[i]==q2[j]:\n",
    "                res.append(q1[i])\n",
    "                res.append(q1[i])\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                res.append(q2[j])\n",
    "                j+=1\n",
    "            if i==len(q1)and j==len(q2):\n",
    "                break\n",
    "            if i>=len(q1):\n",
    "                res=res+q2[j:]\n",
    "            if j>=len(q2):\n",
    "                res=res+q1[i:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def tree(self, root):\n",
    "        if not root: return []\n",
    "        return self.tree(root.left) + [root.val] + self.tree(root.right)\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        return sorted(self.tree(root1)+self.tree(root2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getList(self, root):\n",
    "        if root is None:\n",
    "            return None\n",
    "        res = [root.val]\n",
    "        if root.left is not None:\n",
    "            res = self.getList(root.left) + res\n",
    "        if root.right is not None:\n",
    "            res = res + self.getList(root.right)\n",
    "        return res\n",
    "\n",
    "    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:\n",
    "        res = []\n",
    "        r1 = self.getList(root1)\n",
    "        if r1 is not None:\n",
    "            res += r1\n",
    "        r2 = self.getList(root2)\n",
    "        if r2 is not None:\n",
    "            res += r2\n",
    "        return sorted(res)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
